package zby;

import javax.sound.midi.Soundbank;

public class LeetCode_70 {

    /**
     * 70. 爬楼梯
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * <p>
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * <p>
     * 注意：给定 n 是一个正整数。
     *
     * @param args
     */
    public static void main(String[] args) {
        LeetCode_70 code = new LeetCode_70();

        long s = System.currentTimeMillis();
        System.out.println(code.climbStairs2(50));
        long e = System.currentTimeMillis() - s;
        System.out.println(e);
    }


    /**
     * 超出时间限制	N/A	N/A
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n < 2) {
            return 1;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }


    /**
     * 0 ms	34.9 MB
     *
     * @param n
     * @return
     */
    public int climbStairs1(int n) {
        arr = new int[n];
        return clim(n);
    }

    private int[] arr;

    private int clim(int n) {
        if (n < 2) {
            return 1;
        }
        int t = arr[n - 1];
        if (t == 0) {
            t = clim(n - 1) + clim(n - 2);
            arr[n - 1] = t;
        }
        return t;
    }

    /**
     * 0 ms	34.8 MB
     *
     * @param n
     * @return
     */
    public int climbStairs2(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

}
